#!/usr/bin/python3
# _*_ coding:utf-8 _*_


import random
from caltime import runtime


def sift(ls, low, high):
    """
    :param ls:列表
    :param low:堆的根节点位置
    :param high:堆的最后一个元素的位置
    :return:
    """
    i = low  # i 最开始指向根节点
    j = 2 * i + 1  # j 开始是指向左孩子
    tmp = ls[low]  # 把堆顶存起来
    while j <= high:  # 只要j位置有数
        if j + 1 <= high and ls[j + 1] > ls[j]:  # 如果右孩子有且比较大
            j = j + 1  # j指向右孩子
        if ls[j] > tmp:
            ls[i] = ls[j]
            i = j          # 往下看一层
            j = 2 * i + 1
        else:   # 如果tmp更大，把tmp放到i的位置上
            ls[i] = tmp
            break
    else:
        ls[i] = tmp  # 把tmp放到i的位置上


@runtime
def heap_sort(ls):
    n = len(ls)
    # 开始建大根堆
    for i in range((n - 1 - 1) // 2, - 1, -1):
        # i表示建堆的时候调整的部分的根的下标
        sift(ls, i, n - 1)
    # 堆建完了
    # 下面开始挨个出数
    for i in range(n - 1, -1, -1):
        # i指向当前堆的最后一个位置
        ls[0], ls[i] = ls[i], ls[0]
        sift(ls, 0, i - 1)  # i - 1是新的high


lst = [random.randint(-1000, 1000) for _ in range(100)]
# print('原列表>>>', lst)
heap_sort(lst)
# print('排序后的列表>>>', lst)

